前言
本文为布里斯托大学推出的52 Things Every PhD Student Should Know to do Cryptography系列学习笔记中的第一篇。原文连接：52 Things:Number 1 : Different Types of Processors。
核心问题
本篇的核心问题可以概括为以下问题：
- 通用处理器
- 具有指令集扩展的通用处理器
- 专用处理器或协同处理器
- FPGA
以上四种硬件的差异体现在哪些方面？
通用处理器
尽管通用处理器没有严格的定义，但是将具有图灵完备的处理器称为通用处理器这一理论被广泛接受。通用处理器包含可以计算任何实际可计算的处理器，它们都可以解决图灵机可以解决的任何问题。在现代处理器背景下，大多数可编程CPU被认为是通用的。
具有指令集扩展的通用处理器
处理器达到通用目的的代价通常会导致性能方面的不足。换句话说，通用处理器也许能够计算任何可计算的东西，但其无法胜任复杂的重复任务。针对那些各类应用程序中在通用处理上有规律地重复执行的任务，处理器设计师可以通过将指令集扩展合并到基本微体系结构中来适应该类任务。尽管微体系结构在功能上差异不大，但实际上用户会获得巨大的性能提升。对于CPU来说，基本的指令集相差甚微，但是许多厂家为了提升某一方面的性能，又开发了扩展指令集，扩展指令集定义了新的数据和指令，能够大大提高某方面数据处理的能力，但是对软件支持提出了新的需求。
我们举一个有关指令集扩展的密码学示例——具有AES加密磁盘的台式机。
该情况下，任何从二级存储（即磁盘）中读取的数据，都需要一个CPU中断来先对数据块进行解密，然后才能加载到内存处理。由于从缓存访问磁盘会影响访问性能，这就需要在磁盘上增加一个解密程序，于是一个值得重新考虑磁盘加密的瓶颈出现了。显然，AES加密是我们选择的复杂重复任务，给定一个简单指令集的通用CPU，我们别无选择只能以线性流操作的方法实现解密。Intel和AMD都意识到磁盘加密的需求，并且自2010年以来完成了AES-NI x86指令集扩展的生产，从而加快了台式机CPU系列磁盘加密的速度。
专用处理器/协同处理器
如果希望针对任何计算进行全面加速，最优选择就是专用处理器或专用集成电路ASIC。这样可以实现性能提升，但作为代价会失去通用处理器的灵活性。这些类型的处理器通常紧密耦合到通用处理器中，因此称为协同处理器。需要注意的是，协同处理器可能与通用处理器存在于同一封装体系，但不一定集成到通用体系结构中。如果我们将目光转向现代处理器体系结构，Intel和AMD都将声卡、图形处理器和DSP引擎集成到了它们的CPU中，这种情况下附加功能通过专用寄存器公开，协同处理器被当作单独组件由通用处理器进行管理。
Field Programmable Gate Array
场可编程门阵列处于通用处理器和专用处理器的中间地带。如果一个应用需要高性能的吞吐量，同时对修改次数要求较少，那么FPGA可能是最好的选择。
FPGA的工作原理说明如下：参考一个非常大的电子面包板，其周围遍布成千上万个逻辑门和查找表（通过多路复用的方式附着于内存）。如果将应用描述为一组门和时序约束的集合，那么可以在电路板上用导线将其连接形成一个电路，该电路可以用于计算目标应用。一个FPGA能提供可重编程的灵活性，同时通过生成专用逻辑电路来计算一个目标应用。与通用程序相比，FPGA需要使用硬件描述语言（VHDL或Verilog）来设计和构建你的应用。
当然，FPGA并非没有缺点。对于大型应用，使用低级构建模块来设计程序是非常麻烦的。此外与通用嵌入式集成电路相比，其具有更高的能耗和硬件成本。由于制造商Xilinx将ARM通用核装载在FPGA上，并封装在一个单独的包中。这使得FPGA可以作为ARM核的一个灵活的协同处理器进行使用，因此可以构建专门的逻辑电路来检测密码原语，以便实现密码操作的加速。
总结
通用处理器能够计算任何可以计算的任务。
拥有指令集扩展的通用处理器与通用处理器类似，不过其针对一些特定的应用能够更高效地执行。
专用处理器/协同处理器在计算一些特定任务时很快，但无法计算其它应用。
FPGA可以用于构建以上所有硬件，但是与ASIC比较，其通过牺牲速度的方法来保证灵活性。
CPU与FPGA的根本区别在于软件和硬件的差异。CPU为冯诺依曼结构，串行地执行一系列指令；而FPGA可以实现并行操作。一般来说，CPU可以实现的功能，都可以通过硬件设计的方法由FPGA实现。
附加：图灵机与图灵完备
上述通用处理器的定义过程中运用到图灵完备的相关知识，以前也接触过这个概念但一直没有仔细记录，现特记录如下。
图灵机 Turing Machine
图灵机是图灵在1936年发表的On Computable Numbers, with an Application to the Entscheidungsproblem中提出的数学模型。在文章中图灵描述了它的具体定义，并且证明了只要图灵机可以被实现，就可以用来解决任何可计算问题。
图灵机由以下几个部分构成：
- 一条无限长的纸带(tape)，纸带被分成一个个相邻的格子(square)，每个格子都可以写上至多一个字符(symbol)。
- 一个字符表(alphabet)即字符的集合，它包含纸带上可能出现的所有字符。特殊字符blank意味着此格子中没有任何字符。
- 一个读写头(head)，可以理解为指向其中一个格子的指针。它可以实现对当前格子内容的读取/写入/擦除，此外也可以每次向左/右移动一个格子。
- 一个状态寄存器(state register)，它追踪着每一步运算过程中，整个机器所处的状态，包含运行和终止两个状态。当状态从运行变为终止时，运算结束，机器停机并交回控制权。
- 一个有限的指令集(instructions table)，它记录着读写头在特定情况下应该执行的行为。
有两点需要注意：
- 计算开始前，纸带可以是完全空白或者在某些格子里预先初始化数据。
- 运算开始时，读写头从某一位置开始，严格按照此刻的配置（当前所处位置+当前格子内容）来一步步对照指令集进行操作，直到状态变为停止。
假设上述模型提到的功能都能被以某种形式物理实现，那么任意可计算问题均可被解决。这里的计算问题泛指一切与计算相关的问题。
A computational problem is a mathematical object representing a collection of questions that computers might be able to solve.
也存在一些不可计算的计算问题，比如著名的停机问题(Halting Problem)。
Halting Problem: given the description of an arbitrary program and a finite input, decide whether the program finished running or will run forever.
该问题是一个不可计算问题即不存在一个通用算法，可以在任意输入下解决此问题。
图灵完备 Turing Completeness
图灵完备性是针对一套数据操作规则而言的概念。数据操作规则可以是编程语言，也可以是计算机里具体实现的指令集。当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。下面我们以一套编程语言为例对图灵完备性质进行说明。
Brainfuck语言
Brainfuck is fully Turing-complete.
首先它存储数据的方式是一个不限长的一维整数数组，里面的数值全部初始化为0.此外有一数据指针，每一时刻都指向数组的某一元素，指针可以向左/向右移动，也可以对当前值进行读取/修改。该语言由8个有效字符组成，分别为：
>指针向右移动一格
<指针向左移动一格
+指针当前指向格子中的数值加一
-指针当前指向格子中的数值减一
.把当前指向格子中的数值按照ASCII表输出到终端
,从终端接受一字节的数据，将其ASCII数值存储到当前格
[当指针当前值为0时，跳转到与之对应的
]符号之后，否则程序正常执行]程序跳转回与之对应的
[处
可以看到，该语言针对数域上的运算引入了加法和减法（乘法可以分解为加法而除法可以分解为减法），针对ASCII码与字母的转换引入了转换符号，针对循环问题引入了循环符号，同时引入左移右移符号从而控制每个格子。解决了可计算问题，符合图灵机的定义，故该语言图灵完备。
此外，Brainfuck还可以用于检测编程语言的完备性。对于一个语法功能复杂的新语言，使用数学证明的方式确定性说明其图灵完备较为麻烦，但是只要能够使用这门新语言实现一个Brainfuck解释器，那么就可以证明其图灵完备。
可视化Brainfuck语言运作流程：Brainfuck Visualizer。
图灵完备判断
对于一个编程语言，我们可以通过它是否能够模拟出图灵机的运作流程来判断其是否具有图灵完备性。例如，图灵不完备的语言常见原因有循环或递归受限（即无法写出不终止的程序），无法开辟数组和列表这一类数据结构（无法模拟无限长的纸带）。
